package com.lry.basic.algorithm.common;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/6/28
 */
//数组中某个数字出现次数超过数组大小一半，找出该数
    //思路一 partition一次中间的数即是所找
    //思路二 保留两个标志数，一个是该数组元素，一个是该元素出现的次数
public class FindNum {
    public static void main(String[] args) {
        int[] arr={2,1,3,1,1,3,1};
        System.out.println(findNum(arr));
        //partition算法要求可以改变数组元素位置
        partition(arr,0,arr.length-1);
        System.out.println(arr[arr.length/2]);
    }
    //思路二 不要求可以改变数组元素位置
    private static int findNum(int[] arr) {
        int ele=arr[0],num=1;
        for(int i=1;i<arr.length;i++){
            if(arr[i]==ele){
                num++;
            }else{
                if(num>0){
                    num--;
                }else{
                    ele = arr[i];
                    num = 1;
                }
            }
        }
        return ele;
    }

    public static int partition(int[] arr,int i,int j){
        while(j>i){
            //右侧扫描
            while(j>i&&arr[j]>=arr[i]){
                j--;
            }
            //交换后i++
            if(j>i){
                swap(arr,i,j);
                i++;
            }

            //左侧扫描
            while(j>i&&arr[j]>=arr[i]){
                i++;
            }
            //交换后j--
            if(j>i){
                swap(arr,i,j);
                j--;
            }
        }
        return i;
    }

    public static void swap(int[] arr, int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
